As is well known, a solid state drive (SSD) is a data storage device that uses a non-volatile memory to store data. After data are written to the flash memory, if no electric power is supplied to the flash memory, the data are still retained in the solid state drive. FIG. 1 is a schematic functional block diagram illustrating a conventional solid state drive. As shown in FIG. 1, the solid state drive 10 comprises a controlling circuit 110, a buffering circuit 130 and a non-volatile memory 120. The controlling circuit 110 is in communication with a host 12 through an external bus 20. Consequently, commands and data can be exchanged between the controlling circuit 110 and the host 12. Generally, the external bus 20 is a USB bus, an SATA bus, a PCIe bus, or the like. For example, the buffering circuit 130 is a volatile memory such as a dynamic random access memory (DRAM).
Moreover, the storage space of the buffering circuit 130 is divided into plural storage areas. For example, the first storage area of the buffering circuit 130 is a data buffering area 132. The write data from host 12 or the valid data to be moved during a garbage collection of the non-volatile memory 120 can be temporarily stored in the data buffering area 132. For example, when the host 12 intends to store the write data into the non-volatile memory 120, the write data received by the controlling circuit 110 through the external bus 20 are temporarily stored into the data buffering area 132. Alternatively, while the garbage collection of the non-volatile memory 120 is performed by the controlling circuit 110, the valid data to be moved are temporarily stored into the data buffering area 132. Moreover, the write data or the valid data are written from the data buffering area 132 to the non-volatile memory 120 at proper time. A second storage area of the buffering circuit 130 is used for storing a flash translation layer table (FTL table) 136. The data in the non-volatile memory 120 of the solid state drive 10 can be quickly accessed by the controlling circuit 110 through the FTL table. The functions of the FTL table 136 will be described as follows.
Generally, the host 12 defines the data addresses of the solid state drive 10 through logical block addresses (LBAs). Moreover, the non-volatile memory 120 defines the data addresses of the non-volatile memory 120 through physical allocation addresses (PAAs). Consequently, the solid state drive 10 should have a FTL table for mapping LBA into PAA. The FTL table is stored in the buffering circuit 130.
For example, when a write command is issued from the host 12, a LBA is also issued from the host 12 to notify the controlling circuit 110 to store the write data into the LBA. Then, the PAA of the non-volatile memory 120 for storing the write data is determined by the controlling circuit 110. Moreover, the relationship between the LBA and the PAA is recorded in the FTL table 136 by the controlling circuit 110. According to the recoded contents of the FTL table 136, the controlling circuit 110 can search the PAA corresponding to the LBA and search the write data from the non-volatile memory 120.
As mentioned above, the relationship between the LBA and the PAA is recorded in the FTL table 136. If the contents of the FTL table 136 are erroneous, the controlling circuit 110 cannot find out the data. In case that electric power is normally supplied to the solid state drive 10, the FTL table 136 is stored in the buffering circuit 130. Consequently, the relationship between the LBA and the PAA can be quickly read, stored and updated.
Before the electric power supplied to the solid state drive 10 is stopped, the FTL table 136 is written back to the non-volatile memory 120 by the controlling circuit 110. After the electric power is no longer supplied to the solid state drive 10, the FTL table 136 stored in the buffering circuit 130 is deleted.
As mentioned above, the FTL table 136 has been written to the non-volatile memory 120 before the electric power supplied to the solid state drive 10 is stopped. Consequently, after the solid state drive 10 is powered again, the FTL table in the non-volatile memory 120 is loaded into the buffering circuit 130 by the controlling circuit 110. Consequently, the solid state drive 10 can be normally operated.
When the controlling circuit 110 intends to move the temporarily-stored data from the data buffering area 132 to the non-volatile memory 120, the controlling circuit 110 selects a first blank block of the non-volatile memory 120 as an open block and provides a block programming serial number to the first blank block. Then, the data in the data buffering area 132 are stored into the open block of the non-volatile memory 120.
After the open block is occupied by the data, the controlling circuit 110 will select a second blank block the non-volatile memory 120 as the open block and provide a new block programming serial number to the second blank block. The new block programming serial number is the original new block programming serial number plus one. Then, the data in the data buffering area 132 are stored into the open block of the non-volatile memory 120. In other words, the block programming serial number is associated with the sequence of programming the blocks of the non-volatile memory 120. Except that the solid state drive 10 is formatted to zero the block programming serial number, the block programming serial number of the non-volatile memory 120 gradually increases.
FIGS. 2A˜2H schematically illustrate the actions of the conventional solid state drive. It is assumed that the non-volatile memory 120 has six blocks B1˜B6 and each block has four storage spaces. For example, b11 denotes the PAA of the first storage space of the first block B1, b12 denotes the PAA of the second storage space of the first block B1, and the rest may be deduced by analog. Moreover, the terms “a”, “c”, “e” and “x” denote specified numbers.
Firstly, when the electric power is received by the solid state drive, the contents of the FTL table in a reserved area of the non-volatile memory 120 are loaded into the FTL table 136 of the buffering circuit 130. Please refer to the FTL table 136 of FIG. 2A. Since the PAA b21 is mapped to the LBA (a), the first storage space of the second block B2 stores the data D1 of the LBA (a). Since the PAA b22 is mapped to the LBA (a+3), the second storage space of the second block B2 stores the data D2 of the LBA (a+3). Since the PAA b23 is mapped to the LBA (e), the third storage space of the second block B2 stores the data D3 of the LBA (e). Since the PAA b24 is mapped to the LBA (c+1), the fourth storage space of the second block B2 stores the data D4 of the LBA (c+1). The rest of the FTL table 136 may be deduced by analog.
Moreover, the block programming serial numbers (SN) of the second block B2, the fifth block B5 and the third block B3 are (x), (x+1) and (x+2), respectively. Consequently, the second block B2 is firstly programmed, then the fifth block B5 is programmed, and finally the third block B3 is programmed. Moreover, the FTL table 136 also records the last block programming serial number (i.e., SN:x+2) before the previous normal shutdown. After the solid state drive 10 is powered again, the controlling circuit 110 can confirm the storing condition of the non-volatile memory 120 according to the contents of the FTL table 136. After the controlling circuit 110 confirms the storing condition, the solid state drive 10 is in the normal working state.
Please refer to FIG. 2B. The solid state drive 10 is in the normal working state. The controlling circuit 110 receives a write command from the host 12. The write command intends to provide data D5′, D2′, D11′ and D8′ to update the data D5, D2, D11 and D8 in the LBAs (a+2)˜(a+5). Meanwhile, the data D5′, D2′, D11′ and D8′ are temporarily stored in the data buffering area 132.
Please refer to FIG. 2C. The controlling circuit 110 selects the first block B1 as the open block, and provides the block programming serial number (x+3) to the first block B1. Moreover, the block programming serial number in the FTL table 136 is updated (i.e., SN:x+3). Then, the data D5′, D2′, D11′ and D8′ in the data buffering area 132 are written into the four storage spaces of the open block (i.e., the first block B1) by the controlling circuit 110, and the FTL table 136 is updated. Generally, in addition to the data D5′, D2′, D11′ and D8′, the LBAs corresponding to the data D5′, D2′, D11′ and D8′ are also stored in the four storage spaces of the first block B1 of the non-volatile memory 120.
Please refer to FIG. 2C again. Since the data D5′, D2′, D11′ and D8′ are stored in the open block (i.e., the first block B1), the PAAs (b11)˜(b14) in the FTL table 136 are mapped to the LBAs (a+2)˜(a+5), respectively. Moreover, the PAAs (b31), (b22), (b53) and (b34) storing the old data D5, D2, D11 and D8 are mapped to the invalid LBA (FF). In the FTL table 136 as shown in FIG. 2C, the data in the storage spaces corresponding to the PAAs (b31), (b22), (b53) and (b34) are invalid data.
Please refer to FIG. 2D. The controlling circuit 110 receives a write command from the host 12. The write command intends to provide data D3′, D9′, D7′ and D12′ to update the data D3, D9, D7 and D12 in the LBAs (e)˜(e+3). Meanwhile, the data D3′, D9′, D7′ and D12′ are temporarily stored in the data buffering area 132.
Please refer to FIG. 2E. The controlling circuit 110 selects the sixth block B6 as the open block, and provides the block programming serial number (x+4) to the sixth block B6. Moreover, the block programming serial number in the FTL table 136 is updated (i.e., SN:x+4). Then, the data D3′, D9′, D7′ and D12′ in the data buffering area 132 are written into the four storage spaces of the open block (i.e., the sixth block B6) by the controlling circuit 110, and the FTL table 136 is updated.
Please refer to FIG. 2E again. Since the data D3′, D9′, D7′ and D12′ are stored in the open block (i.e., the sixth block B6), the PAAs (b61)˜(b64) in the FTL table 136 are mapped to the LBAs (e)˜(e+3), respectively. Moreover, the PAAs (b23), (b51), (b33) and (b54) storing the old data D3, D9, D7 and D12 are mapped to the invalid LBA (FF). In the FTL table 136 as shown in FIG. 2E, the data in the storage spaces corresponding to the PAAs (b23), (b51), (b33) and (b54) are invalid data.
In case that the non-volatile memory 120 contains a great number of invalid data, the controlling circuit 110 performs a garbage collection. Consequently, the valid data D6 and D10 in the third block B3 and the fifth block B5 are moved to the data buffering area 132 by the controlling circuit 110. While the garbage collection is performed, the controlling circuit 110 can still receive the command from the host. As shown in FIG. 2F, the controlling circuit 110 receives a write command from the host 12. The write command intends to provide a data D13 to the LBA (c+2) and provide an updated data D11″ to the LBA (a+4). In addition, the data D13 and D11″ are also stored in the data buffering area 132.
Please refer to FIG. 2G. The controlling circuit 110 selects the fourth block B4 as the open block, and provides the block programming serial number (x+5) to the fourth block B4. Moreover, the block programming serial number in the FTL table 136 is updated (i.e., SN:x+5). Then, the data D6, D10, D13 and D11″ in the data buffering area 132 are written into the four storage spaces of the open block (i.e., the fourth block B4) by the controlling circuit 110, and the FTL table 136 is updated.
Please refer to FIG. 2G again. Since the data D6 and D10 are stored in the open block (i.e., the fourth block B4), the PAAs (b32) and (b52) storing the old data D6 and D10 are mapped to the invalid LBA (FF). Moreover, the PAAs (b41), (b42), (b43) and (b44) in the FTL table 136 are mapped to the LBAs (c), (a+1), (c+2) and (a+4), respectively. Moreover, in the FTL table 136, the PAA (b13) storing the old data D11′ is mapped to invalid LBA (FF). The data in the storage spaces corresponding to the invalid LBA (FF) are invalid data. In the FTL table 136 as shown in FIG. 2G, the data in the storage spaces corresponding to the PAAs (b13), (b32) and (b52) are invalid data. Moreover, the data in the storage spaces corresponding to the PAAs (b31)˜(b34) and (b51)˜(b54) are also invalid data. Consequently, the data in the storage spaces of the third block B3 and the fifth block B5 are all invalid data.
As mentioned above, the data in the storage spaces of the third block B3 and the fifth block B5 are all invalid data. Consequently, after the valid data are moved in the garbage collection, the third block B3 and the fifth block B5 are erased as the blank blocks (see FIG. 2H). Under this circumstance, the block programming serial numbers (x+2) and (x+1) are also erased. Moreover, after the FTL table 136 is updated, the PAAs (b31)˜(b34) and (b51)˜(b54) have no mapping relationship to the LBAs. According to the contents of the FTL table 136, the third block B3 and the fifth block B5 become the blank blocks.
If a shutdown command is received by the controlling circuit 110 in the situation of FIG. 2H, it means that the solid state drive 10 will be normally shut down. Consequently, after the contents of the FTL table 136 are stored to the reserved area of the non-volatile memory 120 by the controlling circuit 110, the electric power supplied to the solid state drive 10 is interrupted. Moreover, after the solid state drive 10 is powered again, the FTL table in the non-volatile memory 120 is loaded into the FTL table 136 of the buffering circuit 130 by the controlling circuit 110. Consequently, the solid state drive 10 can be normally operated.
However, if the solid state drive 10 in the situation of FIG. 2H is not normally shut down, some problems may occur. For example, since the controlling circuit 110 does not receive the shutdown command from the host 12, the contents of the FTL table 136 in the buffering circuit 130 cannot be immediately stored to the non-volatile memory 120. That is, the contents of the FTL table 136 in the buffering circuit 130 disappear.
For solving the above problems, the controlling circuit 110 realizes that the previous power interruption is resulted from an abnormal shutdown according to a power flag after the solid state drive 10 is powered again. Then, the controlling circuit 110 has to rebuild the contents of the FTL table 136. After the contents of the FTL table 136 are rebuilt, the solid state drive 10 can be normally operated. A conventional method of rebuilding the contents of the FTL table 136 after the solid state drive 10 in the situation of FIG. 2H is suffered from abnormal shutdown will be described as follows.
FIGS. 3A˜3E schematically illustrate a conventional method of rebuilding the FTL table of the solid state drive. In case that the solid state drive 10 is powered again after the abnormal shutdown, the contents of the FTL table 136 corresponding to the previous shutdown are not reserved in the reserved area of the non-volatile memory 120.
Please refer to FIG. 3A. The contents of the non-volatile memory 120 are identical to those of the non-volatile memory 120 as shown in FIG. 2H. Moreover, the contents of the FTL table 136 are identical to the contents of the FTL table 136 as shown in FIG. 2A because the contents of the FTL table 136 as shown in FIG. 2A are stored before the previous normal shutdown. Moreover, the controlling circuit 110 realizes that the previous power interruption is resulted from an abnormal shutdown according to a power flag. Consequently, it is necessary to rebuild the FTL table.
As shown in FIG. 3A, the controlling circuit 110 realizes that only the FTL table 136 corresponding to the block programming serial number (x+2) is updated according to the block programming serial number (i.e., SN:x+2). Consequently, it is necessary to sequentially update the FTL table 136 from the block programming serial number (x+2) to the largest block programming serial number.
Please refer to FIG. 3B. The controlling circuit 110 updates the FTL table 136 to the block programming serial number (SN:x+3), and reads the contents of the first block B1 corresponding to the block programming serial number (x+3). As mentioned above, the storage spaces of the blocks in the non-volatile memory 120 not only store data but also store the LBAs corresponding to the data. Consequently, while the controlling circuit 110 reads the contents of the first block B1 corresponding to the block programming serial number (x+3), the stored data and the corresponding LBAs are also acquired. In this embodiment, the data D5′, D2′, D11′ and D8 in the first storage space, the second storage space, the third storage space and the fourth storage space of the first block B1 correspond to the LBAs (a+2), (a+3), (a+4) and (a+5), respectively. Consequently, the controlling circuit 110 updates the FTL table 136. That is, the PAA (b11) corresponds to the LBA (a+2), the PAA (b12) corresponds to the LBA (a+3), the PAA (b13) corresponds to the LBA (a+4), and the PAA (b14) corresponds to the LBA (a+5). Moreover, after the PAA (b31) corresponding to the LBA (a+2) is updated, the PAA (b31) corresponds to the invalid LBA (FF). After the PAA (b22) corresponding to the LBA (a+3) is updated, the PAA (b22) corresponds to the invalid LBA (FF). After the PAA (b53) corresponding to the LBA (a+4) is updated, the PAA (b53) corresponds to the invalid LBA (FF). After the PAA (b34) corresponding to the LBA (a+5) is updated, the PAA (b34) corresponds to the invalid LBA (FF).
Please refer to FIG. 3C. The controlling circuit 110 updates the FTL table 136 to the block programming serial number (SN:x+4), and reads the contents of the sixth block B6 corresponding to the block programming serial number (x+4). In this embodiment, the data D3′, D9′, D7′ and D12′ in the four storage spaces of the sixth block B6 correspond to the LBAs (e), (e+1), (e+2) and (e+3), respectively. Consequently, the controlling circuit 110 updates the FTL table 136. That is, the PAA (b61) corresponds to the LBA (e), the PAA (b62) corresponds to the LBA (e+1), the PAA (b63) corresponds to the LBA (e+2), and the PAA (b64) corresponds to the LBA (e+3). Moreover, after the PAA (b23) corresponding to the LBA (e) is updated, the PAA (b23) corresponds to the invalid LBA (FF). After the PAA (b51) corresponding to the LBA (e+1) is updated, the PAA (b51) corresponds to the invalid LBA (FF). After the PAA (b33) corresponding to the LBA (e+2) is updated, the PAA (b33) corresponds to the invalid LBA (FF). After the PAA (b54) corresponding to the LBA (e+3) is updated, the PAA (b54) corresponds to the invalid LBA (FF).
Please refer to FIG. 3D. The controlling circuit 110 updates the FTL table 136 to the block programming serial number (SN:x+5), and reads the contents of the fourth block B4 corresponding to the block programming serial number (x+5). In this embodiment, the data D6, D10, D13 and D11″ in the four storage spaces of the fourth block B4 correspond to the LBAs (c), (a+1), (c+2) and (a+4), respectively. Consequently, the controlling circuit 110 updates the FTL table 136. That is, the PAA (b41) corresponds to the LBA (c), the PAA (b42) corresponds to the LBA (a+1), the PAA (b43) corresponds to the LBA (c+2), and the PAA (b44) corresponds to the LBA (a+4). Moreover, after the PAA (b32) corresponding to the LBA (c) is updated, the PAA (b32) corresponds to the invalid LBA (FF). After the PAA (b52) corresponding to the LBA (a+1) is updated, the PAA (b52) corresponds to the invalid LBA (FF). After the PAA (b13) corresponding to the LBA (a+4) is updated, the PAA (b13) corresponds to the invalid LBA (FF).
Since the largest block programming serial number in the non-volatile memory 120 is (x+5), the contents of the FTL table 136 as shown in FIG. 3D are arranged by the controlling circuit 110. Moreover, since all of the PAAs (b31)˜(b34) and (b51)˜(b54) correspond to the invalid LBA (FF), the controlling circuit 110 confirms that the third block B3 and the fifth block B5 are the blank blocks. Consequently, after the FTL table 136 is updated, the PAAs (b31)˜(b34) and (b51)˜(b54) have no mapping relationship to the LBAs (see FIG. 3E).
Obviously, the contents of FIG. 3E are completely identical to the contents of FIG. 2H. Meanwhile, the FTL table 136 is successfully rebuilt by the controlling circuit 110, and the FTL table 136 is restored to the state before the abnormal shutdown. Consequently, the solid state drive 10 can be normally operated.
FIG. 4 is a flowchart illustrating a method of rebuilding the FTL table of the solid state drive according to prior art. After the solid state drive 10 receives electric power (Step S410), the controlling circuit 110 loads the contents of the FTL table from the reserved area of the non-volatile memory 120 and builds the FTL table 136 in the buffering circuit 130 (Step S420).
Then, the controlling circuit 110 judges whether an abnormal shutdown event occurs according to a power flag (Step S430). If no abnormal shutdown event occurs, the solid state drive 10 is normally operated (Step S450). Whereas, if the abnormal shutdown event occurs, the contents of the blocks of the non-volatile memory 120 corresponding to the block programming serial numbers larger than the block programming serial number of the FTL table 136 are sequentially read, and the PAA-LBA mapping relationship in the FTL table 136 is updated (Step S440). Then, the solid state drive 10 is normally operated (Step S450).